#include "bfsalgorithm.h"
#include <queue>
#include <set>
#include <algorithm>

BFSAlgorithm::BFSAlgorithm()
    : SearchAlgorithm("宽度优先搜索(BFS)")
{
}

//closedset 有序不重复
SearchResult BFSAlgorithm::search(const PuzzleState& initial, const PuzzleState& goal)
{
    // 设置目标状态
    goalState = goal;
    
    // 检查可解性
    if (!initial.isSolvable(goal)) {
        SearchResult result;
        result.success = false;
        result.algorithmName = algorithmName;
        return result;
    }
    
    // 重置计数器
    resetCounters();
    
    // 记录开始时间
    auto startTime = std::chrono::high_resolution_clock::now();
    
    // 使用队列存储待扩展节点
    std::queue<std::shared_ptr<SearchNode>> openQueue;
    
    // 使用集合存储已访问状态
    std::set<PuzzleState> closedSet;
    
    // 创建初始节点
    auto initialNode = std::make_shared<SearchNode>(initial);
    openQueue.push(initialNode);
    nodesGenerated++;
    
    while (!openQueue.empty()) {
        // 获取队列前端的节点
        auto currentNode = openQueue.front();
        openQueue.pop();
        
        // 检查是否已访问过此状态
        if (closedSet.find(currentNode->getState()) != closedSet.end()) {
            continue;
        }
        
        // 标记为已访问
        closedSet.insert(currentNode->getState());
        nodesExpanded++;
        
        // 检查是否到达目标状态
        if (currentNode->getState() == goal) {
            // 构建解路径
            std::vector<PuzzleState> path;
            auto node = currentNode;
            while (node) {
                path.push_back(node->getState());
                node = node->getParent();
            }
            std::reverse(path.begin(), path.end());
            
            // 记录结束时间
            auto endTime = std::chrono::high_resolution_clock::now();
            auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime);
            
            SearchResult result;
            result.success = true;
            result.algorithmName = algorithmName;
            result.path = path;
            result.steps = path.size() - 1;
            result.nodesGenerated = nodesGenerated;
            result.nodesExpanded = nodesExpanded;
            result.timeElapsed = duration.count();
            
            return result;
        }
        
        // 扩展当前节点
        std::vector<PuzzleState> successors = currentNode->getState().getSuccessors();
        for (const auto& successor : successors) {
            // 跳过已访问的状态
            if (closedSet.find(successor) != closedSet.end()) {
                continue;
            }
            
            // 创建后继节点
            auto successorNode = std::make_shared<SearchNode>(successor, currentNode);
            openQueue.push(successorNode);
            nodesGenerated++;
        }
    }
    
    // 未找到解
    auto endTime = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(endTime - startTime);
    
    SearchResult result;
    result.success = false;
    result.algorithmName = algorithmName;
    result.nodesGenerated = nodesGenerated;
    result.nodesExpanded = nodesExpanded;
    result.timeElapsed = duration.count();
    
    return result;
}